Comparative Analysis of Numerous Routing Protocols of Mobile

Ad hoc Network

Saurabh Shivhare*, Nischol Mishra, Jitendra Singh Verma

SOIT, RGPV, Bhopal (M.P.) India

*Corresponding Author Email: nicksaurabh2007@gmail.com

ABSTRACT:

In this paper, we can focus on various routing protocols of mobile adhoc network which are categorized into proactive, reactive and hybrid. These can be further divided into number of protocols. Proactive protocols determine the routing path at the time up of start up and maintain the routing table while Reactive routing protocols determine routing information as and when needed. It means no prior information about routing is collected. Hybrid routing protocols are a newly generated protocols, which are having nature of both proactive and reactive protocols. The hybrid routing protocols employ both reactive and proactive properties by maintaining intra-zone information proactively and inter-zone information reactively. These various protocols are subjected to studies in contrast of time complexity and communication complexity with their compensation and limitations. It was concluded the basic possible concepts on different protocols being used in MANETs. Thus, it was tried to analyze and compare them in accordance with the protocol being used in the network. We have used parameters such packet drop ratio, throughput, latency, applicability, scalability which are used for comparative analysis between various routing protocols. This paper discusses the open research issues on routing protocol of ad hoc network. We have discussed Proactive Protocol (DSDV, WRP, GSR, FSR), Reactive Protocol (AODV, DSR, LMR, LAR) and Hybrid Protocol (ZRP, ZHLS, SLURP, DST). “Paper formatting is very poor”

“I have done various changes in the abstract but it is not sufficient, so re correct it because abstract is very important. Do not use the definition of routing protocol in the abstract, write down the name of routing protocol which shows the high performance in the respect of various parameters. ” Remove the grammatical and spelling mistakes and increase the number of references. “Do follow the IEEE format” Reduces the number of pages, uses the main heading Abstract, Introduction, Routing protocols, challenges in routing, comparative analysis, conclusion, references. After check the pplagiarism of the paper. It should contain only 20% copy paste data from other resources

KEYWORDS:

INTRODUCTION:

It has been collectively recognized that the speedy development of computer and information technology in the last twenty years has primarily changed almost every field in science and engineering. In Last few decades it has seen a swift growth of research interests in mobile ad hoc networking.[1] Ad hoc network is a multi-hop wireless network, which consists of numeral of mobile nodes. These nodes produce traffic to be forwarded to some other nodes or a group of nodes. Due to a dynamic nature of ad hoc networks, conservative fixed network routing protocols are not possible. Based on that reason quite a few proposals for routing protocols has been presented. Ad hoc radio networks have various realization areas. Some areas to be mentioned are military, emergency, conferencing and sensor applications. Each of these function areas has their specific necessities for routing protocols.[2] Compared to wired networks, mobile networks have unique characteristics. In mobile networks, lump mobility may cause repeated network topology changes, which are rare in restless networks. In distinction to the stable link capacity of wired networks, wireless link capacity repeatedly varies since of the impacts from broadcast power, headset sensitivity, noise, fading and meddling. Additionally, wireless mobile networks have a high fault rate, power restrictions and bandwidth limitations.

Dynamic research work for mobile ad hoc network is carrying on mainly in the fields of intermediate entrance control, routing, supply management, power control and safety. Because of the importance of routing protocols in dynamic multi-hop networks, a lot of mobile ad hoc network routing protocols have been proposed in the last few years. There are some challenges that make the design of mobile ad hoc network steering protocols a tough task. [3] In the present work, various protocols namely proactive, reactive and hybrid are subjected to studies in contrast of time complexity and communication complexity with their compensation and limitations.

Proactive Routing Protocol:

In proactive protocol, each node determines the routing path at the time up of start up and maintains the routing table. Each node periodically updates the table and shares the information with other nodes about their updated table. It means that routes to all other destinations or nodes are determined at the start up, and maintained through using a periodic route update process. In other words, each node maintains routing information to every other node or nodes located in a specific part in the network. The routing information is usually kept in a number of different tables. These tables are periodically updated. Proactive routing protocols maintain consistent, up-to-date routing information from each node to every other node in the network. These protocols require each node to maintain one or more tables to store routing information, and they respond to changes in network topology by propagating updates throughout the network in order to maintain a consistent network view. [4,5,6]

Proactive Routing Protocol can be classified in

· Destination-sequenced distance vector (DSDV)

· Wireless routing protocol (WRP)

· Global state routing (GSR)

· Fisheye State Routing (FSR)

· Source Tree Adaptive Routing (STAR)

· Distance Routing effect algorithm for Mobility

(DREAM)

· Multimedia support in mobile wireless networks

(MMWN)

· Cluster-head gateway switch routing (CGSR)

· Hierarchical state routing (HSR)

· Optimized link state routing (OLSR)

· Topology broadcast reverse path forwarding (TBRPF)

Comparative Analysis of Proactive Routing Protocols:

Here we compare various routing protocol on the basis of various parameter like routing structure, No. of Tables, Frequency of updates, hello messages, critical nodes and Characteristics features.

Protocol	Routing Structure	No. of Tables	Frequency of Updates	Hello Message	Critical Nodes	Characteristic Features
DSDV	Flat	2	Periodic and as required	Yes	No	Loop free
WRP	Flat	4	Periodic	Yes	No	Loop freedom using predecessor info
GSR	Flat	3 and list	Periodic and local	No	No	Localised updates
FSR	Flat	3 and list	Periodic and local	No	No	Controlled frequency of updates
STAR	Hierarchical	1 and 5 list	Conditional	No	No	Minimise control Overhead
DREAM	Flat	1	Mobility based	No	No	Controlled rate of updates by mobility and distance
MMWN	Hierarchical	Maintains a database	Conditional	No	Yes, Location Manager	minimized control Overhead
CGSR	Hierarchical	2	Periodic	No	Yes, Cluster Head	Clusterheads exchange routing information
HSR	Hierarchical	2	Periodic	No	Yes, Cluster Head	Low control Overhead
OLSR	Flat	3	Periodic	Yes	No	Reduced control Overhead
TBRPF	Flat	1 and 4 list	Periodic and differential	Yes	Yes, Parent node	Broadcasting topology

Advantages and Disadvantages of Proactive Routing Protocols:

Here we will discuss various advantages and disadvantages of various proactive routing Protocols

Protocol	Advantages	Disadvantages
DSDV	Loop free	High overhead
WRP	Loop free	Memory overhead
GSR	Localized updates	High Memory Overhead
FSR	Reduces Control Overhead	High Memory Overhead, Reduced accuracy
STAR	Low Control Overhead	High Memory Overhead and Processing Overhead
DREAM	Low Control Overhead and Memory Overhead	Requires a GPS
MMWN	Low Control Overhead	Mobility management and cluster maintenance
CGSR	Reduced Control Overhead	cluster formation and maintenance
HSR	Low Control Overhead	location management
OLSR	Reduced Control Overhead and contention	2-hop neighbor knowledge required
TBRPF	Low Control Overhead	High Memory Overhead

Complexity Comparison of Proactive Routing Protocol

Protocol	Convergence Time	Memory Overhead	Control Overhead
DSDV	O(D.I)	O(N)	O(N)
WRP	O(h)	O(N.N)	O(N)
GSR	O(D.I)	O(N.N)	O(N)
FSR	O(D.I)	O(N.N)	O(N)
STAR	O(D)	O(N.N)	O(N)
DREAM	O(N.I)	O(N)	O(N)
MMWN	O(2D)	O(N)	O(X+E)
CGSR	O (D)	O(2.N)	O(N)
HSR	O(D)	O(N.N.L)+O(S)+O(N/S)+O(N/n)	O(n.L)/I +O(1)/J
OLSR	O(D.I)	O(N.N)	O(N.N)
TBRPF	O(D) or D+2 for link Failure	O(N.N)+O(N)+O(N+V)	O(N.N)

Reactive Routing Protocol:

In reactive routing Protocol, each node determines routing information as and when needed. It means no prior information about routing is collected. Routing information is collected when node wants to transmit the data. This type of routing protocol is also called On-demand routing protocol. Reactive Routing Protocol or On-demand routing protocols were developed to minimize the overheads in proactive protocols by maintaining information for active routes only. This means that routes are determined and maintained for nodes that require sending data to a particular destination. This process reduces the overhead of maintain routing information of inactive nodes or nodes which are passive in the network. In reactive routing Protocol, Route discovery usually done by passing a route request packets in the network. When a node with a route to the destination is reached a route reply is sent back to the source node using link reversal if the route request has travelled through bi-directional links or by piggy-backing the route in a route reply packet via flooding. Therefore, the route discovery overhead becomes very less as compared to Proactive routing Protocol. Reactive type of routing creates routes only when required by the source node. When a node requires a route to a destination, it initiates a route discovery process within the network.

This process is completed once a route is found or all possible route permutations and combination have been examined. Once a route has been examined and established, it is maintained by a route maintenance procedure until either the destination becomes inaccessible along every path from the source or until the route is no longer desired. When a source node desires to send a message to some destination node and does not already have a valid route to that destination, it initiates a path discovery process to locate the other node. [7,8]

Routing Protocol can be classified as following:

· Ad hoc On-demand distance vector (AODV)

· Dynamic Source Routing (DSR)

· Light-weight mobile routing (LMR)

· Location-aided routing (LAR)

· Temporally ordered routing algorithm (TORA)

· Routing On-demand Acyclic Multi-path (ROAM)

· Associatively-based routing (ABR)

· Flow oriented routing protocol (FORP)

· Relative distance micro-discovery ad hoc routing

(RDMAR)

· Ant-colony-based routing algorithm (ARA)

· Cluster-based routing protocol (CBRP)

· Signal stability adaptive (SSA)

Comparative Analysis of Reactive Routing Protocols:

Here we compare various Reactive routing protocol on the basis of various parameter like routing structure, multiple routes, beacons, route metric method, route maintained in, and route reconfiguration strategy.

Protocol	Routing Structure	Multiple routes	Bea-cons	Route metric method	Route maintained in	Route reconfiguration strategy
AODV	Flat	No	Yes	Shortest Path and freshest	Route Table	Erase route then Source Notification
DSR	Flat	Yes	No	Shortest Path or available in cache	Route Cache	Erase route then Source Notification
ROAM	Flat	Yes	No	Shortest Path	Route Table	Erase route
LMR	Flat	Yes	No	Shortest Path or available in cache	Route Table	Link reversal and Route repair
TORA	Flat	Yes	No	Shortest Path or available in cache	Route Table	Link reversal and Route repair
ABR	Flat	No	Yes	Shortest Path and strong associavity	Route Table	Erase route then Source Notification
SSA	Flat	No	Yes	Strongest signal strength and stability	Route Table	Erase route then Source Notification
RDMAR	Flat	No	No	Shortest relative distance or Shortest Path	Route Table	Erase route then Source Notification
LAR	Flat	Yes	No	Shortest Path	Route Cache	Erase route then Source Notification
ARA	Flat	Yes	No	Shortest Path	Route Table	Use alternate route or back track until a route is found
FORP	Flat	No	No	First available route	Route Table	A Flow_HANDOFF used to use alternate route
CBRP	Hierarchic-al	No	No	First available route	Route Table	Erase route then Source Notification and local route repair.

Advantages and Disadvantages Reactive Routing Protocol

Here we will discuss various advantages and disadvantages of various Reactive routing Protocols

Protocol	Advantages	Disadvantages
AODV	Adaptable to highly dynamic topologies	Scalability problems, large delays, hello messages
DSR	Multiple routes, Promiscuous overhearing	Scalability problems due to source routing and flooding, large delays
ROAM	Elimination of search-to-infinity problem.	Large CO in highly mobile environments
LMR	Multiple routes	Temporary routing loops
TORA	Multiple routes	Temporary routing loops
ABR	Route stability	Scalability problem
SSA	Route stability	Scalability problems, large delays during route failure and reconstruction
RDMAR	Localised route discovery	Flooding used if there is no prior communication between nodes
LAR	Localised route discovery	Based on source routing, flooding is used if no location information is available
ARA	Low overhead, small control packet size	Flooding based route discovery process
FORP	Employees a route failure minimisation technique	Flooding based route disovery process
CBRP	Only cluster-heads exchange routing information	Cluster maintenance, temporary loops

Complexity Comparison of Reactive Routing Protocol

Protocol	Time complexity in route discovery	Communication complexity in route discovery
AODV	O(2D)	O(2N)
DSR	O(2D)	O(2N)
ROAM	O(D)	O(mode E)
LMR	O(2D)	O(2N)
TORA	O(2D)	O(2N)
ABR	O(B+P)	O(N+R)
SSA	O(B+P)	O(N+R)
RDMAR	O(2S)	O(2M)
LAR	O(2S)	O(2M)
ARA	O(D+P)	O(N+R)
FORP	O(D+P)	O(N+R)
CBRP	O(2D)	O(2X)

Where

D-Diameter of the network;

N -number of nodes in the network;

B-diameter of the affected area;

S -diameter of the nodes in the localised region;

P - Diameter of the directed path

E- Number of edges in the network.

X - Number of clusters

Hybrid Routing Protocol:

It is a combination of Proactive and reactive routing Protocol. Hybrid routing protocols are a newly generated protocols, which are having nature of both proactive and reactive protocols. These protocols are developed to increase scalability by allowing nearby nodes or nodes with close proximity to work together to make some sort of a backbone to reduce the route discovery overheads and make route discover easier. Most hybrid protocols proposed till date are zone-based, which means that the network is partitioned or seen as a number of zones by each node. Hybrid routing protocols have the potential to provide higher applicability and scalability than pure reactive or proactive protocols. This is because they attempt to minimize the number of rebroadcasting nodes by defining a structure which allows the nodes to work together in order to organize how routing is to be performed. By working together the best or the most suitable nodes can be used to perform route discovery. Hybrid routing protocols attempt to eliminate single point of failures and creating blockage nodes in the network. This is achieved by allowing any number of nodes to perform routing or data forwarding if the preferred path becomes unavailable. [9]

The DDR algorithm consists of six phases:

· Preferred neighbor election,

· Forest construction,

· Intra-tree clustering,

· Inter-tree clustering,

· Zone naming

· Zone partitioning.

Comparative analysis of Hybrid Protocols:

Protocol	Routing Structure	Multiple routes	Beacons	Route metric method	Route maintained in	Route reconfiguration strategy
ZRP	Flat	No	Yes	Shortest Path	Intra zone and Inter zone tables	Route repair at point of failure and Source Notification
ZHLS	Hierarchical	Yes	No	Shortest Path or available in virtual link	Intra zone and Inter zone tables	Location request
SLURP	Hierarchical	Yes	No	MFR for inter zone For warding. DSR for intra zone routing	location cache and a node_list	Source Notification then location discovery
DST	Hierarchical	Yes	No	Forwarding using the tree neighbours and the bridges using shuttling	Route Table	Holding timec or shuttling
DDR	Hierarchical	Yes	Yes	Stable routing	Intra zone and Inter zone table	Source Notification then source initiates a new path discovery

Comparative Analysis between Proactive, Reactive and Hybrid Routing Protocol:

Here we compare the Proactive protocol, Reactive protocol and Hybrid protocol on the basis of following Parameters.

Parameters	Proactive Protocol	Reactive Protocol	Hybrid Protocol
Basic Feature	1. Each node determines the routing path at the time up of start up.	1. Each node determines routing information as and when needed.	It proactively maintains routes to nearby nodes and determine routes to far away nodes with the help of a route discovery strategy
Table	2. Each node to maintain one or more tables to store routing information.	2.Node maintains routing table for active route only	2. It depends on routing strategy.
Routing	3.Each Node maintain sequence no. to reach other nodes	3.Each node pass a route request packets in the network to reach other nodes	3. Zone-based, which means that the network is partitioned or seen as a number of zones by each node.
Applicable	4.Lower applicability	4.Medium applicability	4. higher applicability
Scalable	5.Lower scalability	5.Medium scalability	5.higher scalability
Accuracy	6.High accuracy	6.Medium accuracy	6.Medium Accuracy
Overhead	7.High overhead	7.Low overhead	7.Low Overhead
Memory	8.High Memory overhead	8.Low Memory overhead	8.Low Memory overhead
Path	9. Shortest path is used.	9. Discovered route is used.	9. The best or the most suitable nodes can be used to perform route discovery.

Advantages and Disadvantages of Hybrid protocol

Here we will discuss various advantages and disadvantages of various Hybrid routing Protocols

Protocol	Routing Structure	Multiple routes
ZRP	Reduce retransmissions	Overlapping zones
ZHLS	Reduction of SPF, low Control Overhead	Static zone map required
SLURP	Location discovery using home regions	Static zone map required
DST	Reduce retransmissions	Root node
DDR	No zone map or zone coordinator	Preferred neighbours may become bottlenecks

Complexity Comparison of Hybrid protocol

Protocol	Time complexity in route discovery	Communication Complexity in route discovery
ZRP	Intra: O(I) Inter: O(2D)	Intra: O(Z) Inter: O(N+V)
ZHLS	Intra: O(I) Inter: O(D)	Intra: O(N/M) Inter: O(N+V)
SLURP	Intra: O(Z) Inter: O(D)	Intra: O(2N/M) Inter: O(Y)
DST	Intra: O(Z) Inter: O(D)	Intra: O(Z)/O (N)
DDR	Intra: O(I) Inter: O(2D)	Intra: O(Z) Inter: O(N+V)

Fig 1 Comparison of Throughput v/s Number of nodes in Fig. 2 Comparison of Delay v/s Simulation Time

Proactive Routing Protocol in Proactive Routing Protocol

CONCLUSION:

In the present work it can provide metaphors of various routing schemes proposed for ad hoc mobile networks. It also makes available a categorization of these schemes according to the routing strategy. It has obtainable a comparison of these categories of routing protocols, highlighting their features, differences and characteristics. It was done comparative analysis of routing protocols based on various parameters. Finally, it has identified probable applications and challenges facing ad hoc mobile wireless networks. The hybrid routing protocols employ both reactive and proactive properties by maintaining intra-zone information proactively and inter-zone information reactively. Reactive routing protocols such as the TORA and DSR may also perform well in large networks. Hybrid Protocols are combination of reactive protocol and proactive protocols. So there is a need to more focus on these protocols. It can develop more hybrid protocols by using good features of reactive and proactive protocols so that they can work efficiently. The field of ad hoc mobile networks is rapidly growing and changing, and while there are still many challenges that need to be met, it is likely that such networks will see widespread use within the next decades.

REFERENCES:

1. E.M. Royer, CK. Toh, “A Review of Current Routing Protocols for Ad-Hoc Mobile Wireless Networks”, IEEE Personal Communications Magazine, pp. 46-55, April 1999.

2. N. Nikaein, H. Labiod, C. Bonnet, “DDR Distributed Dynamic Routing Algorithm for Mobile Ad-Hoc Networks”, Proceedings of the First Annual Workshop on Mobile Ad Hoc Network and Computing, MobiHOC , Boston,pages 19-27, August 2000.

3. L.M. Feeney: “A Taxonomy for Routing Protocols in Mobile Ad Hoc Networks”, SICS TechnicalReport pages 07-09, October 1999.

4. Mehran Abolhasan, Tadeusz Wysocki, Eryk Dutkiewicz, “A review of routing protocols for mobile ad hoc networks”, Ad Hoc Networks 2,PP 1–22, 2004.

5. M. Gerla, C.-C. Chiang, and L. Zhang, “Tree Multicast Strategies in Mobile, Multihop Wireless Networks”,ACM/Baltzer Mobile Networks and Apps. Journal, pp.8-11, 1998.

6. S. Singh, M. Woo, and C. S. Raghavendra, “Power-Aware Routing in Mobile Ad Hoc Networks”, Proc. ACM/IEEE MOBICOM, pp.23-25, Oct. 1998.

7. Y. B. Ko and N. H. Vaidya, “Location-Aided Routing (LAR) in Mobile Ad Hoc Networks”, Proc. ACM/IEEE MOBICOM , pp 38-40, Oct. 1998

8. P. W. Yau and C. J. Mitchell, “Reputation Methods for Routing Security for Mobile Ad Hoc Networks”, IST Workshop. Mobile Future and Symp. Trends in Communications, Bratislava, Slovakia, pp. 28-31 Oct. 2003.

9. S. Yi, P. Naldurg, and R. Kravets, “A Security-Aware Routing Protocol for Wireless Ad Hoc Networks”, Proc. ACM MobiHoc, 2001.

Received on 26.12.2014 Accepted on 26.02.2015

Research J. Engineering and Tech. 6(2): April-June, 2015 page 231-237

DOI: 10.5958/2321-581X.2015.00034.3